package io.tec.cloud.algorithm.c04_v20220613;

import io.tec.cloud.algorithm.AlgorithmUtil;

/**
 * 在一个数组中，任何一个前面的数a，和任何一个后面的数b，
 * 如果(a,b)是降序的，就称为降序对。
 * 给定一个数组arr，求数组的降序对总数量
 */
public class T29_ReversePair {

    public static int reversePair1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
//        if (arr.length == 2) {
//            return arr[0] > arr[1] ? 1 : 0;
//        }

        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int l, int r) {
        // base case
        if (l == r) {
            return 0;
        }
        // TODO 位运算优先级
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    /**
     * 从右向左遍历，arr[l]>arr[r]时，产生逆序对；相等时，copy右组
     */
    private static int merge(int[] arr, int l, int mid, int r) {
        int li = mid;
        int ri = r;
        int[] help = new int[r - l + 1];
        int idx = help.length - 1;
        int count = 0;
        while (li >= l && ri >= mid + 1) {
            count += arr[li] > arr[ri] ? ri - mid : 0;
            help[idx--] = arr[li] > arr[ri] ? arr[li--] : arr[ri--];
        }
        while (li >= l) {
            help[idx--] = arr[li--];
        }
        while (ri >= mid + 1) {
            help[idx--] = arr[ri--];
        }

        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return count;
    }


    public static int reversePair2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
//        if (arr.length == 2) {
//            return arr[0] > arr[1] ? 1 : 0;
//        }
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            // TODO j从i下一个开始
            for (int j = i + 1; j < arr.length; j++) {
                count += arr[i] > arr[j] ? 1 : 0;
            }
        }
        return count;
    }


    public static void main(String[] args) {
        int testTimes = 100_0000;
        int maxValue = 100;
        int maxLength = 100;
        for (int t = 0; t < testTimes; t++) {
            int[] arr = AlgorithmUtil.generateArray(maxValue, AlgorithmUtil.random(maxLength));
            int[] arr1 = AlgorithmUtil.copyArray(arr);
            int[] arr2 = AlgorithmUtil.copyArray(arr);
            int count1 = reversePair1(arr1);
            int count2 = reversePair2(arr2);
            if (count1 != count2) {
                AlgorithmUtil.printArray(arr);
                System.out.println("error");
                break;
            }
        }
        System.out.println("finish");
    }
}
